package org.taoge;

/**
 * @author weipt
 * @description 冒泡排序
 * @date 2024/5/29 21:33
 */
public class BubbleSort {

    public static void main(String[] args) {
        int[] arr1 = {1, 33, 3, 5, 4, 6,9, 8, 99, 10};
        int[] arr2 = {10, 9, 8, 7, 6, 5,4, 3, 2, 1};
        int[] arr3 = {1, 2, 3, 4, 5, 6,7, 8, 9, 10};
        int[] ints1 = bubbleSort(arr1);
        int[] ints2 = bubbleSort(arr2);
        int[] ints3 = bubbleSort(arr3);
        for (int i : ints1) {
            System.out.print(i);
        }
        System.out.println();

        for (int i : ints2) {
            System.out.print(i);
        }
        System.out.println();

        for (int i : ints3) {
            System.out.print(i);
        }

        /**
         * 结果分析：
         * 如果没有优化介入，整体都需要45次，如果有介入，就可以优化循环此时
         * 优化介入，排序次数：10
         * 优化介入，排序次数：45
         * 优化介入，排序次数：0
         */
    }


    /**
     * 冒泡排序
     * @param arr
     * 1、关于i和j的初始值与循环次数，大家写的时候，不用太关注，等写完后，再去调试
     * 如果我们if(arr[j] > arr[j+1])，则我们的for中，次数就是arrLength-i-1;
     * 如果我们if(arr[j-1] > arr[j])，则我们的for中，次数就是arrLength-i;
     * 总之防止越界就行，同时注意，j的循环要和i联动
     * @return
     */
    public static int[] bubbleSort(int[] arr) {
        int arrLength = arr.length;
        int num = 0;
        for(int i =0; i< arrLength; i++){  //外部循环遍历，循环次数为数组长度-1
            boolean isSorted = true;  //任意一次循环中，没有发生交换，则说明数组已经有序，可以提前结束循环
            for(int j = 0; j< arrLength-i-1; j++){  //内部每次遍历，第一次length，第二次length-1，依次类推，等差
                if(arr[j] > arr[j+1]){ //我们从小到大排序，不满足情况的就是前面的比后面大，此时才需要我们进行交换位置
                    //如何记住：基本思想就是，把前面的给后面，然后把后面的给前面
                    //如果没有temp介入，一旦把后面的赋值给前面，前面和后面都一样，所以在赋值前先把被覆盖的存起来
                    int temp = arr[j];  //把大数存起来
                    arr[j] = arr[j+1];  //把小数存到前面
                    arr[j+1] = temp;    //把大数存到后面
                    isSorted = false;
                    num ++;
                }
            }
            if(isSorted){
                System.out.println("优化介入，排序次数：" + num);
                return arr;
            }
        }
        System.out.println("排序次数：" + num);
        return arr;
    }
}
